home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / qlib205.zip / QLIB.ZIP / SRC / QLIB / ALLOC.ASM < prev    next >
Assembly Source File  |  1997-04-01  |  8KB  |  361 lines
  1. include qlib.inc
  2. include errno.inc
  3. include string.inc
  4.  
  5. ; Fragmented Memory Manager
  6.  
  7. ; All I do is keep simple 12 byte headers in front of each block of RAM.
  8. ; First 2 byte = 'PQ'.  Second = flags. (a junk byte here ). Then next dword
  9. ; is a pointer to the previous block header and the next dword is the size
  10. ; of this block.  Flags are used to tell if a block is free and/or last one.
  11.  
  12. ; All alloc RAM will be dword aligned
  13.  
  14. .data
  15. externdef _baseram:dword     ;... don't want user to touch cause malloc sceme may change
  16.                              
  17. ;RAM header
  18. heads struct  ;12bytes
  19.   magic dw ? ; 'PQ' ;signature (it will be 'QP' thru out this file cause of intel byte swap)
  20.   flag db ?  ;bit0=free(1)  bit1=last(2)   (1==true)
  21.   _a1 db ?   ;junk byte for alignment (not used!)
  22.   prev dd ?  ;ptr=>previous block
  23.   siz dd ?   ;size of this block
  24. heads ends
  25.  
  26. MB_FREE equ 1
  27. MB_LAST equ 2
  28.  
  29. .code
  30.  
  31. malloc proc,sz:dword
  32.   pushad
  33.   cmp sz,0
  34.   jnz @f
  35. bad:
  36.   popad
  37.   mov errno,ENOMEM
  38.   mov eax,NULL
  39.   ret
  40. @@:
  41.   ;make sure alloc block is dword aligned
  42.   add sz,3
  43.   and sz,0ffffffffh-3
  44.   ;search thru chain for best fit
  45.   mov eax,_baseram  ;ram start
  46.   .if !eax
  47.     jmp bad
  48.   .endif
  49.   mov ebx,0     ;best fit location
  50.   mov ecx,-1    ;best fit is ecx too much over sz
  51. start:
  52.   mov dl,[eax].heads.flag
  53.   test dl,1  ;free?
  54.   jnz ok3
  55. next:
  56.   mov dl,[eax].heads.flag
  57.   test dl,2  ;last?
  58.   jnz endsrc
  59.   add eax,[eax].heads.siz
  60.   add eax,sizeof heads
  61.   jmp start
  62. ok3:
  63.   ;found one that's free
  64.   mov edx,[eax].heads.siz
  65.   sub edx,sz
  66.   jb next ;too small
  67.   ;found one big enough
  68.   cmp edx,ecx
  69.   jae next ;already got another that's better
  70.   ;this one's better
  71.   mov ecx,edx
  72.   mov ebx,eax
  73.   jmp next
  74. endsrc:
  75.   ;end of search
  76.   cmp ebx,0
  77.   jz bad
  78. ;split ebx into 2 blocks:1st = used 2nd = free
  79.   mov eax,ebx
  80.   xor [ebx].heads.flag,1  ;set as used!
  81.   cmp ecx,256  ;don't make a really small block
  82.   ja ok4
  83.   add ecx,sz
  84.   mov [ebx].heads.siz,ecx  ;set size (all of it)
  85.   add eax,sizeof heads
  86.   mov [esp+7*4],eax
  87.   popad
  88.   ret
  89. ok4:
  90.   mov edx,sz
  91.   mov al,[ebx].heads.flag
  92.   and al,2        ;mask last
  93.   xor [ebx].heads.flag,al  ;remove last if it's there
  94.   mov [ebx].heads.siz,edx ;set size
  95.   add edx,ebx
  96.   add edx,sizeof heads
  97.   mov [edx].heads.magic,'QP'  ;free only
  98.   mov [edx].heads.flag,1
  99.   or [edx].heads.flag,al  ;set if last
  100.   mov [edx].heads.prev,ebx  ;set prev
  101.   sub ecx,sizeof heads
  102.   mov [edx].heads.siz,ecx  ;set size
  103.   mov eax,ebx
  104.   add eax,sizeof heads
  105.   mov [esp+7*4],eax
  106.   popad
  107.   ret
  108. malloc endp
  109.  
  110. calloc proc,siz1:dword,siz2:dword   ;it's like size,n_size type thing
  111.   ;this clears the alloc RAM to 0
  112.   local siz:dword
  113.   pushad
  114.   mov eax,siz1
  115.   mov ebx,siz2
  116.   mul ebx
  117.   mov siz,eax
  118.   callp malloc,eax
  119.   .if eax==NULL
  120.     popad
  121.     mov eax,NULL
  122.     ret
  123.   .endif
  124.   mov [esp+7*4],eax  ;save for ret
  125.   mov edi,eax
  126.   mov eax,0
  127.   mov ecx,siz
  128.   mov ebx,ecx
  129.   shr ecx,2
  130.   rep stosd
  131.   mov ecx,ebx
  132.   and ecx,3
  133.   .if !zero?
  134.     rep stosb
  135.   .endif
  136.   popad
  137.   ret
  138. calloc endp
  139.  
  140. free proc,b:dword
  141.   pushad
  142.   mov eax,b
  143.   cmp eax,0
  144.   jnz ok6
  145. bad:
  146.   popad
  147.   mov errno,ENOMEM   ;just ignore
  148.   mov eax,ERROR
  149.   ret
  150. ok6:
  151.   sub eax,sizeof heads
  152.   cmp eax,_baseram
  153.   jz ok7 ;no above!
  154.   mov ebx,[eax].heads.prev
  155.   test [ebx].heads.flag,1
  156.   jz ok7
  157.   ;above is free
  158.  
  159.   mov dl,[eax].heads.flag  ;must copy flags to above block
  160.   mov ecx,[eax].heads.siz
  161.   mov eax,ebx
  162.   add ecx,sizeof heads
  163.   add [eax].heads.siz,ecx
  164.   mov [eax].heads.flag,dl
  165. ok7: ;done joining with above block
  166.   mov ebx,[eax].heads.siz
  167.   add ebx,eax
  168.   add ebx,sizeof heads
  169.   test byte ptr[ebx].heads.flag,1
  170.   jz ok8
  171.   mov ecx,[ebx].heads.siz
  172.   add ecx,sizeof heads
  173.   add [eax].heads.siz,ecx
  174.   mov dl,[ebx].heads.flag
  175.   mov [eax].heads.flag,dl
  176. ok8: ;done joining below
  177.   or [eax].heads.flag,1  ;mark as free
  178.   popad
  179.   xor eax,eax
  180.   ret
  181. free endp
  182.  
  183. qfree proc ;query free ram  ;out:eax=largest
  184.   pushad
  185.   mov ecx,_baseram
  186.   .if !ecx
  187.     popad
  188.     xor eax,eax
  189.     ret
  190.   .endif
  191.   xor eax,eax  ;largest
  192.   xor edx,edx  ;size of last block
  193.   sub ecx,sizeof heads
  194. start:
  195.   add ecx,sizeof heads
  196.   add ecx,edx
  197.   mov edx,[ecx].heads.siz
  198.   test [ecx].heads.flag,1
  199.   jz nope       ;FIX : v2.03 Beta #4 : this was jumping no where before?
  200.   cmp edx,eax
  201.   jb nope       ;FIX : v2.03 Beta #4 : this was jbe ?
  202.   mov eax,edx
  203. nope:
  204.   test [ecx].heads.flag,2
  205.   jz start
  206.   mov [esp+7*4],eax
  207.   popad
  208.   ret
  209. qfree endp
  210.  
  211. coreleft proc ;query free ram  ;out:eax=total
  212.   pushad
  213.   mov ecx,_baseram
  214.   .if !ecx
  215.     popad
  216.     xor eax,eax
  217.     ret
  218.   .endif
  219.   xor ebx,ebx  ;total
  220.   xor edx,edx  ;size of last block
  221.   sub ecx,sizeof heads
  222. start:
  223.   add ecx,sizeof heads
  224.   add ecx,edx
  225.   mov edx,[ecx].heads.siz
  226.   test [ecx].heads.flag,1
  227.   jz @f
  228.   add ebx,edx
  229. @@:
  230.   test [ecx].heads.flag,2
  231.   jz start
  232.   mov [esp+7*4],ebx
  233.   popad
  234.   ret
  235. coreleft endp
  236.  
  237. ;reallocs a block of RAM
  238. ;this may return a new block addr and it will copy the old block to the new one
  239. realloc proc,p:dword,siz:dword
  240.   ;1st: attempts to see if next block is free and the simple enlarges
  241.   ;     the block as needed
  242.   ;ELSE alloc a new block and copies to it and then releases old block
  243.  
  244.   ;1st part not implemented yet (other more important stuff to do)
  245.  
  246.   local tmp:dword
  247.   .if p==NULL
  248.     callp malloc,siz
  249.     ret
  250.   .endif
  251.   mov eax,p
  252.   sub eax,sizeof heads     ;FIX : v2.00 Beta #4 : this was after .if
  253.   .if wptr[eax].heads.magic!='QP'
  254.     mov eax,NULL  ;ERROR!!
  255.     ret
  256.   .endif
  257.   pushad
  258.   mov ebx,[eax].heads.siz
  259.   .if ebx==siz  ;requested same size
  260.     popad
  261.     mov eax,p   ;nothing to do
  262.     ret
  263.   .endif
  264.   .if ebx<siz
  265.     ;make smaller
  266.     mov ecx,ebx
  267.     sub ecx,siz
  268.     .if ecx<256
  269.       ;don't make the new block too small
  270.       popad
  271.       mov eax,p
  272.       ret
  273.     .endif
  274.     ;split p into 2 blocks!
  275.     mov ebx,siz
  276.     mov edx,[eax].heads.siz
  277.     mov [eax].heads.siz,ebx
  278.     mov cl,[eax].heads.flag
  279.     mov ebx,eax
  280.     add ebx,siz
  281.     add ebx,sizeof heads
  282.     mov [ebx].heads.magic,'QP'
  283.     mov [ebx].heads.flag,cl
  284.     or [ebx].heads.flag,1   ;set as free
  285.     sub edx,siz
  286.     mov [ebx].heads.prev,eax
  287.     sub edx,sizeof heads
  288.     mov [ebx].heads.siz,edx
  289.     popad
  290.     mov eax,p
  291.     ret
  292.   .else
  293.     ;make bigger (if possible)
  294.     ; finished here v2.00 Beta #4
  295.     .if [eax].heads.flag & MB_LAST
  296.       jmp _else ;this is the last one
  297.     .endif
  298.     mov ecx,eax
  299.     add ecx,ebx
  300.     add ecx,sizeof heads  ;FIX : v2.03 Beta #4 : this was missing
  301.     .if ! ([ecx].heads.flag & MB_FREE)
  302.       jmp _else  ;it's not free
  303.     .endif
  304.     mov edx,[ecx].heads.siz
  305.     add edx,sizeof heads
  306.     ;if edx+ebx >= siz then we can do it!
  307.     add edx,ebx
  308.     .if (siz > edx)
  309.       jmp _else
  310.     .endif
  311.     mov ebx,edx
  312.     sub ebx,siz
  313.     .if ebx<256  ;don't make too small
  314.       mov [eax].heads.siz,edx
  315.       mov bl,[ecx].heads.flag
  316.       and bl,MB_LAST
  317.       or [eax].heads.flag,bl  ;set last if it was last
  318.     .else
  319.       ;make another block
  320.       mov cl,[ecx].heads.flag
  321.       and cl,MB_LAST
  322.       mov ebx,siz
  323.       mov [eax].heads.siz,ebx
  324.       mov [eax].heads.flag,0
  325.       add eax,ebx
  326.       mov [eax].heads.magic,'QP'
  327.       mov [eax].heads.flag,MB_FREE
  328.       or [eax].heads.flag,cl  ;set last if needed
  329.       sub edx,siz
  330.       sub edx,sizeof heads
  331.       mov [eax].heads.siz,edx
  332.       mov ebx,p
  333.       mov [eax].heads.prev,ebx
  334.     .endif
  335.     popad
  336.     mov eax,p
  337.     ret
  338.   .endif
  339. _else:    ;alloc a new block and copy to it
  340.   callp malloc,siz
  341.   .if eax==NULL
  342.     popad
  343.     ret
  344.   .endif
  345.   mov tmp,eax
  346.   mov eax,p
  347.   sub eax,sizeof heads
  348.   mov eax,[eax].heads.siz      ;only copy block size
  349.   .if eax>siz
  350.     mov eax,siz                ;unless requested size is smaller
  351.   .endif
  352.   callp memcpy,tmp,p,eax
  353.   callp free,p
  354.   popad 
  355.   mov eax,tmp
  356.   ret
  357. realloc endp
  358.  
  359. end
  360.  
  361.